'效率上：公式优于循环，循环优于递归
'代码量：公式优于递归，递归优于循环
'https://www.cnblogs.com/zkfopen/p/11245857.html
'时间复杂度：O（N2），空间复杂度：O（N）
Function fib(n As Integer) As Double
    If n <= 2 Then
        fibTail = 1
    Else
        fibTail = fib(n - 1) + fibTail(n - 2)
    End If
End Function

'循环
'时间复杂度：O（N），时间复杂度：O（1）
Function fibB(n As Integer) As Double
    Dim fibNOne%, fibNTwo%, fibN%
    fibNOne = 1: fibNTwo = 1: fibN = 0
    For i = n To 1 Step -1
        fibN = fibNOne + fibNTwo
        fibNTwo = fibNOne
        fibNOne = fibN
    Next i
    fibB = fibN
End Function


'通项公式
'时间复杂度：O（logn），空间复杂度：O（1）
Function fibC(n As Integer) As Double
    fibC = ((((1 + Sqr(5)) / 2) ^ n) - ((1 - Sqr(5)) / 2) ^ n) / Sqr(5)
End Function